package random;

import java.util.Arrays;

/**
 * 翻转图像
 *
 * 给定一个二进制矩阵A，我们想先水平翻转图像，然后反转图像并返回结果。
 * 水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转[1, 1, 0]的结果是[0, 1, 1]。
 * 反转图片的意思是图片中的=0=全部被=1=替换，=1=全部被=0=替换。例如，反转=[0, 1, 1]=的结果是=[1, 0, 0]。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/flipping-an-image
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class L832 {

    public static void main(String[] args) {

        int[][] a = {{1,1,0,0},{1,0,0,1},{0,1,1,1},{1,0,1,0}};
        int[][] ints = flipAndInvertImage(a);
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j < ints[i].length; j++) {
                System.out.print(ints[i][j]);
            }
        }
    }

    public static int[][] flipAndInvertImage(int[][] A) {

        // 就是遍历一次二维数组，先进行数组的倒序，然后反转
        for (int i = 0; i < A.length; i++) {
            for (int j = 0; j < A[i].length / 2 ; j++) {
                int temp = A[i][j];
                A[i][j] = A[i][A[i].length - j - 1];
                A[i][A[i].length - j - 1] = temp;
            }
            for (int j = 0; j < A[i].length; j++) {
                if (A[i][j] == 1) {
                    A[i][j] = 0;
                }else {
                    A[i][j] = 1;
                }
            }
        }
        return A;
    }

    // 官方答案（模拟优化 + 双指针 + 位运算）
    /*
    最直观的做法是首先对矩阵 AA 的每一行进行水平翻转操作，然后对矩阵中的每个元素进行反转操作。该做法需要遍历矩阵两次。
    是否可以只遍历矩阵一次就完成上述操作？答案是肯定的。
    假设矩阵的行数和列数都是 nn，考虑列下标 left 和 right，其中 left<right
    且 left + right=n-1，当 0≤i<n 时，对第 i 行进行水平翻转之后，A[i][left] 和 A[i][right] 的元素值会互换，
    进行反转之后，A[i][left] 和 A[i][right] 的元素值都会改变。

    具体而言，考虑以下四种情况。
    情况一：A[i][left]=0,A[i][right]=0。对第 i 行进行水平翻转之后，A[i][left]=0,A[i][right]=0。
    进行反转之后，A[i][left]=1,A[i][right]=1。
    情况二：A[i][left]=1,A[i][right]=1。对第 i 行进行水平翻转之后，A[i][left]=1,A[i][right]=1。
    进行反转之后，A[i][left]=0,A[i][right]=0。
    情况三：A[i][left]=0,A[i][right]=1。对第 i 行进行水平翻转之后，A[i][left]=1,A[i][right]=0。
    进行反转之后，A[i][left]=0,A[i][right]=1。
    情况四：A[i][left]=1,A[i][right]=0。对第 i 行进行水平翻转之后，A[i][left]=0,A[i][right]=1。
    进行反转之后，A[i][left]=1,A[i][right]=0。

    情况一和情况二是 A[i][left]=A[i][right] 的情况。
    在进行水平翻转和反转之后，A[i][left] 和 A[i][right] 的元素值都发生了改变，即元素值被反转。
    情况三和情况四是 AA[i][left]=A[i][right] 的情况。
    在进行水平翻转和反转之后，A[i][left] 和 A[i][right] 的元素值都发生了两次改变，恢复原状。

    因此，可以遍历矩阵一次即完成水平翻转和反转。
    遍历矩阵的每一行。对于矩阵的第 i 行，初始化 left=0 和 right=n−1，进行如下操作：
    当 left<right 时，判断 A[i][left] 和 A[i][right] 是否相等，如果相等则对 A[i][left] 和 A[i][right] 的值进行反转，
    如果不相等则不进行任何操作；
    将 left 的值加 1，将 right 的值减 1，重复上述操作，直到 left≥right；
    如果 n 是奇数，则上述操作结束时，left 和 right 的值相等，都指向第 i 行的中间元素，此时需要对中间元素的值进行反转。

    作者：LeetCode-Solution
    链接：https://leetcode-cn.com/problems/flipping-an-image/solution/fan-zhuan-tu-xiang-by-leetcode-solution-yljd/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public static int[][] flipAndInvertImage1(int[][] A) {

        int n = A.length;
        for (int i = 0; i < n; i++) {
            int left = 0, right = n - 1;
            while (left < right) {
                if (A[i][left] == A[i][right]) {
                    A[i][left] ^= 1;
                    A[i][right] ^= 1;
                }
                left++;
                right--;
            }
            if (left == right) {
                A[i][left] ^= 1;
            }
        }
        return A;

//        作者：LeetCode-Solution
//        链接：https://leetcode-cn.com/problems/flipping-an-image/solution/fan-zhuan-tu-xiang-by-leetcode-solution-yljd/
//        来源：力扣（LeetCode）
//        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    }
}
